package 中等.动态规划.其他;

/**
 * 如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）
 * 的形式组成的，那么该字符串是 单调递增 的。
 * 给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。
 * 返回使 s 单调递增的最小翻转次数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/flip-string-to-monotone-increasing
 */
public class 将字符串翻转到单调递增_926 {

    public static void main(String[] args) {

        System.out.println(minFlipsMonoIncr("00011000"));

    }

    /**
     * 动态规划
     * dp[i] 表示 s 中 [0,i] 索引的最小翻转次数是多少
     * 分类讨论
     * 如果 s[i] == 1 ，那么前面无论是 000 或者是 001 最小翻转次数不变，dp[i] = dp[i-1]
     * 如果 s[i] == 0 ，那么分为两种情况
     * 1，将 s[i] 前面的 1 全部翻转为 0
     * 2，将 s[i] 翻转为 1 ，dp[i] = dp[i-1] + 1
     * 取较小值
     * 空间复杂度优化
     * dp[i] 只与 dp[i-1] 有关
     *
     * @param s
     * @return
     */
    public static int minFlipsMonoIncr(String s) {
        // 长度为 1 时，无需翻转
        int pre = 0, cur = 0;
        int countOne = s.charAt(0) == '1' ? 1 : 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                cur = pre;
                countOne++;
            } else {
                cur = Math.min(pre + 1, countOne);
                pre = cur;
            }
        }
        return cur;
    }

}
